空间复杂度
空间复杂度
空间复杂度S(n)定义为该算法所消耗的存储空间，是一个算法在运行过程中临时占用存储空间大小的度量
时间复杂度和空间复杂度合称为算法的复杂度。
空间复杂度在衡量什么
- 额外空间：算法为了运行额外申请的内存（不含输入数据本身）
- 常见来源：
- 临时数组/临时变量
- 递归调用栈（每一层递归都会占用栈空间）
- 辅助数据结构（栈、队列、哈希表等）
常见例子直觉
- 原地排序（in-place）通常更省空间（接近 O(1) 额外空间），但可能更复杂
- 递归实现通常比迭代实现更耗栈空间（与递归深度相关）